package com.summer.LanQiao;

import java.util.Arrays;

public class TenSortAlgotirhm {
    //冒泡排序
   static void BubbleSort (int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = i+1; j < arr.length ; j++) {
                if (arr[i]>arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
    //选择排序
    static void SelectSort(int[] arr){
        for (int i = 0; i < arr.length-1 ; i++) {
            int minIndex = i;
            int min = arr[minIndex];
            for (int j = i+1; j <arr.length ; j++) {
                if (min>arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
    }
    //插入排序(经典)
    static void  insertSort(int[] arr){
        int  insertValue = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length ; i++) {
            insertValue = arr[i];
            insertIndex = i-1;
            while(insertIndex>=0&&insertValue<arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1] =insertValue;
        }
    }
    //希尔排序(交换法)
//    static void shellSort(int[] arr){
//       int count = 0;
//       int temp = 0;
//        for (int gap = arr.length/2; gap > 0 ; gap/=2) {
//            for (int i = gap; i < arr.length ; i++) {
//                for (int j = i-gap; j >=0 ; j-=gap) {
//                    if (arr[j]>arr[j+gap]){
//                        temp = arr[j];
//                        arr[j] = arr[j+gap];
//                        arr[j+gap] = temp;
//                    }
//                }
//            }
//
//        }
//    }
    //希尔排序(移位法)推荐！！！！(经典)
    static void shellSort(int[] arr){
        for (int gap = arr.length; gap > 0 ; gap/=2) {
            for (int i = gap; i < arr.length ; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]){
                    while (j - gap > 0 && temp < arr[j - gap]){
                        arr[j] = arr[j - gap];
                        j -= gap ;
                    }
                    arr[j] = temp;
                }
            }
        }
    }
    //快排(经典)
    static  void quickSort(int[] arr,int left,int right){
       int pivot = arr[(left+right)/2];
       int l = left;
       int r = right;
       int temp = 0;
       while (l < r){
           while (arr[l] < pivot){
               l++;
           }
           while (arr[r] > pivot){
               r--;
           }
           if (l >= r) break;
           temp = arr[l];
           arr[l] = arr[r];
           arr[r] = temp;
           if (arr[l] == pivot) r--;
           if (arr[r] == pivot) l++;
       }
       if (l == r){
           l++;
           r--;
       }
       if (left<r)quickSort(arr,left,r);
       if (right>l)quickSort(arr,l,right);

    }
    //归并排序
    static void MergeSort(int[] arr,int left,int right,int[] temp){
      if(left < right){
          int mid = (left + right) / 2;
          MergeSort(arr,left,mid,temp);
          MergeSort(arr,mid+1,right,temp);
          Merge(arr,left,mid,right,temp);
      }
    }
    static void Merge(int[] arr,int left,int mid,int right,int[] temp){
    int i = left;
    int j = mid + 1;
    int t = 0;
    while(i <= mid && j <= right){
        if (arr[i] <= arr[j]){
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }else {
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
    }
    while (i <= mid){
        temp[t] = arr[i];
        t += 1;
        i += 1;
    }
    while (j <= right){
        temp[t] = arr[j];
        t += 1;
        j += 1;
    }
    t=0;
    int tempLeft = left;
    while (tempLeft <= right){
        arr[tempLeft] = temp[t];
        t += 1;
        tempLeft += 1;
    }
    }
    public static void main(String[] args) {
       int N = 8000000;
       int[] arr1 = new int[N];
        for (int i = 0; i < N ; i++) {
            arr1[i] = (int) (Math.random()*N);
        }
        int[] arr = new int[]{9,4,2,8,1,5,3,8,9,4,6,5,7};
        int startTime = (int) System.currentTimeMillis();
        //Arrays.sort(arr1);//无限接近0s 800w
        //BubbleSort(arr1);//10s
        //SelectSort(arr1);//2s
        //insertSort(arr1);//0s
        //shellSort(arr1);//1s 800w
        //quickSort(arr1,0,arr1.length-1);//1s 800w
        int temp[] = new int[arr.length];
        //MergeSort(arr,0,arr.length-1,temp);
        quickSort(arr,0,arr.length-1);
        int endTime = (int) System.currentTimeMillis();
        System.out.println("运行时间:"+(endTime-startTime)/1000+"s");
        System.out.println(Arrays.toString(arr));


    }
}
